import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class sequencing_by_merging {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        System.out.println("请输入待处理数组个数个数：");
        int n = in.nextInt();

        int [] A=new int[n];
        System.out.println("请依次输入数值：");
        for (int i=0;i<n;i++){
            A[i]=in.nextInt();
        }

        System.out.println("输入数组为：");
        for (int i=0;i<n;i++){
            System.out.println(A[i]);
        }

        Mergesort(A);
        System.out.println("排序后的数组为：");
        for (int i=0;i<n;i++){
            System.out.println(A[i]);
        }
    }

    public static void Mergesort(int [] A){
        int n=A.length;
        if(n>1) {
            if (n % 2 == 0) {
                int[] B = new int[n / 2];
                int[] C = new int[n / 2];
                for (int i = 0; i < n / 2; i++) {
                    B[i] = A[i];
                    C[i] = A[i + n / 2];
                }
                Mergesort(B);
                Mergesort(C);
                Merge(B, C, A);
            } else {
                int[] B = new int[n / 2];
                int[] C = new int[n / 2 + 1];
                for (int i = 0; i < n / 2; i++) {
                    B[i] = A[i];
                    C[i] = A[i + n / 2];
                }
                C[n / 2] = A[n - 1];
                Mergesort(B);
                Mergesort(C);
                Merge(B, C, A);
            }
        }
    }

    public static void Merge(int [] B,int [] C,int [] A){
        int i=0,j=0,k=0;
        int p=B.length,q=C.length;
        while (i<p&&j<q){
            if(B[i]<=C[j]){
                A[k]=B[i];
                i=i+1;
            }
            else{
                A[k]=C[j];
                j=j+1;
            }
            k=k+1;
        }
        if(i==p){
            int m=k;
            for(int x=j;x<q;x++){
                A[m]=C[x];
                m++;
            }
        }
        else {
            int m=k;
            for (int x=i;x<p;x++){
                A[m]=B[x];
                m++;
            }
        }
    }
}
